Binary Search 二分查找

二分查找模板总结

四点要素：

• start + 1 < end
• start + (end - start) / 2
• A[mid] ==, <, >
• A[start] A[end] ? target

二分法关键

• 头尾指针，取中点，判断往哪儿走
• 寻找满足某个条件第一个或是最后一个位置
• 保留剩下来一定有解的那一半

Question 1: classical-binary-search

https://www.lintcode.com/en/problem/classical-binary-search/

Find any position of a target number in a sorted array. Return -1 if target does not exist.

Given [1, 2, 2, 4, 5, 5].

For target = 2, return 1 or 2.

For target = 5, return 4 or 5.

For target = 6, return -1.

Explanation

基本的二分查找。

Code

public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int findPosition(int[] A, int target) {
        // Write your code here
        if (A == null || A.length == 0){
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (target == A[mid]) {
                end = mid;
            } else if (target > A[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == A[start]) {
            return start;
        }
        if (target == A[end]) {
            return end;
        }
        return -1;
    }
}

Question 2: First Position of target

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

Code

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        if (nums == null || nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (target == nums[mid]) {
                end = mid;
            } else if (target > nums[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == nums[start]) return start;
        if (target == nums[end]) return end;
        return -1;
    }
}

Question 3: last-position-of-target

给一个升序数组，找到target最后一次出现的位置，如果没出现过返回-1

Code

public class Solution {
    /**
     * @param A an integer array sorted in ascending order
     * @param target an integer
     * @return an integer
     */
    public int lastPosition(int[] A, int target) {
        // Write your code here
        if (A == null || A.length == 0){
            return -1;
        }
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (target == A[mid]) {
                //difference with the above questions
                start = mid;
            } else if (target > A[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        //check end element first
        if (target == A[end]) {
            return end;
        }
        if (target == A[start]) {
            return start;
        }
        return -1;
    }
}

Question 4: search-insert-position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume NO duplicates in the array.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

Code

public class Solution {
    /**
     * param A : an integer sorted array
     * param target :  an integer to be inserted
     * return : an integer
     */
    public int searchInsert(int[] A, int target) {
        // write your code here
        if ( A == null || A.length == 0) return 0;
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (target == A[mid]) {
                return mid;
            } else if (target > A[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target <= A[start]) return start;
        if (target <= A[end]) return end;
        return end + 1;
    }
}

Question 5: Search in a big sorted array

Given a big sorted array with positive integers sorted by ascending order. The array is so big so that you can not get the length of the whole array directly, and you can only access the kth number by ArrayReader.get(k) (or ArrayReader->get(k) for C++). Find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number. Return -1, if the number doesn't exist in the array.

Explanation

本题和上面考察如何在一个array中找到一个数不同的是，这个array会非常大。所以要考虑的是如何“倍增”的问题。增到大于target就可以了，接下来找到最初出现的问题。

Code

class Solution {
    /**
     * @param nums: The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        //write your code here
        if (nums == null || nums.length == 0) return -1;
        int end = 0;
        while (end < nums.length && nums[end] < target) {
          end = end * 2 + 1;
        }
        if (end >= nums.length) end = nums.length - 1;
        int start = 0;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (target == nums[mid]) {
                end = mid;
            } else if (target > nums[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (target == nums[start]) return start;
        if (target == nums[end]) return end;
        return -1;
    }
}